package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 25. K 个一组翻转链表
 * @date 2025/4/23 11:05
 */
public class E25 {

    /**
     * 25. K 个一组翻转链表
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 示例：
     * 给你这个链表：1->2->3->4->5
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode curr = head, prev = sentinel;
        while(curr != null){
            stack.push(curr);
            curr = curr.next;
            if(stack.size() == k){
                ListNode node = stack.pop();
                ListNode start = node;
                while(!stack.isEmpty()){
                    node.next = stack.pop();
                    node = node.next;
                }
                prev.next = start;
                prev = node;
            }
        }
        while(!stack.isEmpty()){
            curr = stack.pop();
        }
        prev.next = curr;
        return sentinel.next;
    }
}
